/**
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 */

import type {Block} from '../diff';

import {
  collapseContextBlocks,
  diffBlocks,
  mergeBlocks,
  readableDiffBlocks,
  splitLines,
} from '../diff';

describe('diffBlocks', () => {
  it('returns a "=" block for unchanged content', () => {
    const lines = splitLines('a\nb\nc\nd\ne\n');
    expect(diffBlocks(lines, lines)).toMatchObject([['=', [0, 5, 0, 5]]]);
  });

  it('returns a "!" block for totally different contents', () => {
    const aLines = splitLines('x\ny\n');
    const bLines = splitLines('a\nb\nc\n');
    expect(diffBlocks(aLines, bLines)).toMatchObject([['!', [0, 2, 0, 3]]]);
  });

  it('returns "= ! =" blocks when a line was changed in the middle', () => {
    const aLines = splitLines('a\nb\nc\nd\ne\n');
    const bLines = splitLines('a\nb\nc\nd1\nd2\ne\n');
    expect(diffBlocks(aLines, bLines)).toMatchObject([
      ['=', [0, 3, 0, 3]],
      ['!', [3, 4, 3, 5]],
      ['=', [4, 5, 5, 6]],
    ]);
  });

  it('matches mdiff.blocks (known good diff algorithm), excluding empty blocks', () => {
    // Test cases are generated by:
    //
    // ```
    // #!sl dbsh
    // import json
    // allblocks = e.mdiff.allblocks
    // cases = []
    // for bits in range(16):
    //     a = ['a\n', 'b\n', 'c\n', 'd\n']
    //     b = [bits & (1 << i) and c.upper() or c for i, c in enumerate(a)]
    //     a = ''.join(a)
    //     b = ''.join(b)
    //     blocks = [[s, l] for l, s in allblocks(a, b) if l[0] < l[1] or l[2] < l[3]] # skip empty blocks
    //     cases.append(json.dumps(blocks).replace(' ', ''))
    // print(' '.join(cases))
    // ```
    //
    // String is used to prettier from wrapping lines.
    const testCaseStr =
      '[["=",[0,4,0,4]]] [["!",[0,1,0,1]],["=",[1,4,1,4]]] [["=",[0,1,0,1]],["!",[1,2,1,2]],["=",[2,4,2,4]]] [["!",[0,2,0,2]],["=",[2,4,2,4]]] [["=",[0,2,0,2]],["!",[2,3,2,3]],["=",[3,4,3,4]]] [["!",[0,1,0,1]],["=",[1,2,1,2]],["!",[2,3,2,3]],["=",[3,4,3,4]]] [["=",[0,1,0,1]],["!",[1,3,1,3]],["=",[3,4,3,4]]] [["!",[0,3,0,3]],["=",[3,4,3,4]]] [["=",[0,3,0,3]],["!",[3,4,3,4]]] [["!",[0,1,0,1]],["=",[1,3,1,3]],["!",[3,4,3,4]]] [["=",[0,1,0,1]],["!",[1,2,1,2]],["=",[2,3,2,3]],["!",[3,4,3,4]]] [["!",[0,2,0,2]],["=",[2,3,2,3]],["!",[3,4,3,4]]] [["=",[0,2,0,2]],["!",[2,4,2,4]]] [["!",[0,1,0,1]],["=",[1,2,1,2]],["!",[2,4,2,4]]] [["=",[0,1,0,1]],["!",[1,4,1,4]]] [["!",[0,4,0,4]]]';
    const testCases: Array<Block[]> = testCaseStr.split(' ').map(s => JSON.parse(s));
    testCases.forEach((expected, bits) => {
      // eslint-disable-next-line no-bitwise
      const hasBit = (i: number): boolean => (bits & (1 << i)) > 0;
      const a = ['a\n', 'b\n', 'c\n', 'd\n'];
      const b = a.map((s, i) => (hasBit(i) ? s.toUpperCase() : s));
      const actual = diffBlocks(a, b);
      expect(actual).toEqual(expected);
    });
  });
});

describe('readableDiffBlocks', () => {
  it('prefers changing insignificant lines to insignificant lines 1', () => {
    // https://stackoverflow.com/questions/40550751/unexpected-result-in-git-diff
    const a = `sub _process_message {
    my ($self, $message) = @_;

    my $method = ref($message) eq 'HASH' ? $message->{method} : undef;

    return $self->send_error(ERROR_REQUEST_INVALID)
        unless defined($method);
`;
    const b = `sub _process_message {
    my ($self, $message) = @_;

    my $time =  [ gettimeofday ];

    my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
    return $self->send_error(ERROR_REQUEST_INVALID)
        unless defined($method);
`;
    // Does not produce this:
    //  sub _process_message {
    //      my ($self, $message) = @_;
    //
    // -    my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
    // +    my $time =  [ gettimeofday ];
    //
    // +    my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
    //      return $self->send_error(ERROR_REQUEST_INVALID)
    //          unless defined($method);
    expect(renderDiff(a, b, readableDiffBlocks)).toMatchInlineSnapshot(`
      " sub _process_message {
           my ($self, $message) = @_;
       
      +    my $time =  [ gettimeofday ];
      +
           my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
      -
           return $self->send_error(ERROR_REQUEST_INVALID)
               unless defined($method);
      "
    `);
  });

  it('prefers changing insignificant lines to insignificant lines 2', () => {
    // https://gitlab.com/jssfr/diffsample/-/compare/bob...alice
    const a = `void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
{
    if (!Chunk_bounds_check(src, src_start, n)) return;
    if (!Chunk_bounds_check(dst, dst_start, n)) return;

    memcpy(dst->data + dst_start, src->data + src_start, n);
}

int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
{
    if (chunk == NULL) return 0;

    return start <= chunk->length && n <= chunk->length - start;
}
`;
    const b = `int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
{
    if (chunk == NULL) return 0;

    return start <= chunk->length && n <= chunk->length - start;
}

void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
{
    if (!Chunk_bounds_check(src, src_start, n)) return;
    if (!Chunk_bounds_check(dst, dst_start, n)) return;

    memcpy(dst->data + dst_start, src->data + src_start, n);
}
`;
    // Does not produce this:
    // -void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
    // +int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
    //  {
    // -    if (!Chunk_bounds_check(src, src_start, n)) return;
    // -    if (!Chunk_bounds_check(dst, dst_start, n)) return;
    // +    if (chunk == NULL) return 0;
    //
    // -    // copy the bytes
    // -    memcpy(dst->data + dst_start, src->data + src_start, n);
    // +    return start <= chunk->length && n <= chunk->length - start;
    //  }
    //
    // -int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
    // +void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
    //  {
    // -    if (chunk == NULL) return 0;
    // +    if (!Chunk_bounds_check(src, src_start, n)) return;
    // +    if (!Chunk_bounds_check(dst, dst_start, n)) return;
    //
    // -    return start <= chunk->length && n <= chunk->length - start;
    // +    memcpy(dst->data + dst_start, src->data + src_start, n);
    //  }
    expect(renderDiff(a, b, readableDiffBlocks)).toMatchInlineSnapshot(`
      "+int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
      +{
      +    if (chunk == NULL) return 0;
      +
      +    return start <= chunk->length && n <= chunk->length - start;
      +}
      +
       void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
       {
           if (!Chunk_bounds_check(src, src_start, n)) return;
           if (!Chunk_bounds_check(dst, dst_start, n)) return;
       
           memcpy(dst->data + dst_start, src->data + src_start, n);
       }
      -
      -int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
      -{
      -    if (chunk == NULL) return 0;
      -
      -    return start <= chunk->length && n <= chunk->length - start;
      -}
      "
    `);
    expect(renderDiff(b, a, readableDiffBlocks)).toMatchInlineSnapshot(`
      "-int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
      -{
      -    if (chunk == NULL) return 0;
      -
      -    return start <= chunk->length && n <= chunk->length - start;
      -}
      -
       void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
       {
           if (!Chunk_bounds_check(src, src_start, n)) return;
           if (!Chunk_bounds_check(dst, dst_start, n)) return;
       
           memcpy(dst->data + dst_start, src->data + src_start, n);
       }
      +
      +int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
      +{
      +    if (chunk == NULL) return 0;
      +
      +    return start <= chunk->length && n <= chunk->length - start;
      +}
      "
    `);
  });

  it('sometimes produces non-minimal diff', () => {
    const a = `b
{
    b1
}

a
{
    a1
}
`;
    const b = `a
{
    a1
}

b
{
    b1
}
`;
    // The regular diff produces the minimal diff with 8 changed lines.
    expect(renderDiff(a, b, diffBlocks)).toMatchInlineSnapshot(`
      "-b
      +a
       {
      -    b1
      +    a1
       }
       
      -a
      +b
       {
      -    a1
      +    b1
       }
      "
    `);
    // The "readable" diff has 10 changed lines, but is easier to read by a human.
    expect(renderDiff(a, b, readableDiffBlocks)).toMatchInlineSnapshot(`
      "-b
      -{
      -    b1
      -}
      -
       a
       {
           a1
       }
      +
      +b
      +{
      +    b1
      +}
      "
    `);
  });

  it('avoids the pitfall of the patience diff flaw', () => {
    // Textbook patience diff will match the unique line "x" unconditionally,
    // and produces suboptimal result deleting and inserting multiple
    // insignificant lines. Our diff uses a simple heuristic to avoid that.
    const a = `{
{
{
x
`;
    const b = `x
{
{
{
`;

    expect(renderDiff(a, b, readableDiffBlocks)).toMatchInlineSnapshot(`
      "+x
       {
       {
       {
      -x
      "
    `);
  });
});

describe('collapseContextBlocks', () => {
  it('collapses everything in a "=" block', () => {
    expect(collapseContextBlocks([['=', [0, 5, 0, 5]]], () => false)).toMatchObject([
      ['~', [0, 5, 0, 5]],
    ]);
  });

  it('collapses the top part of a "=" block', () => {
    expect(
      collapseContextBlocks(
        [
          ['=', [0, 5, 0, 5]],
          ['!', [5, 6, 5, 7]],
        ],
        () => false,
      ),
    ).toMatchObject([
      ['~', [0, 2, 0, 2]],
      ['=', [2, 5, 2, 5]],
      ['!', [5, 6, 5, 7]],
    ]);
  });

  it('collapses the bottom part of a "=" block', () => {
    expect(
      collapseContextBlocks(
        [
          ['!', [0, 2, 0, 3]],
          ['=', [2, 8, 3, 9]],
        ],
        () => false,
      ),
    ).toMatchObject([
      ['!', [0, 2, 0, 3]],
      ['=', [2, 5, 3, 6]],
      ['~', [5, 8, 6, 9]],
    ]);
  });

  it('splits a "=" block in 3 blocks on demand', () => {
    expect(
      collapseContextBlocks(
        [
          ['!', [0, 1, 0, 2]],
          ['=', [1, 10, 2, 11]],
          ['!', [10, 11, 11, 12]],
        ],
        () => false,
      ),
    ).toMatchObject([
      ['!', [0, 1, 0, 2]],
      ['=', [1, 4, 2, 5]],
      ['~', [4, 7, 5, 8]],
      ['=', [7, 10, 8, 11]],
      ['!', [10, 11, 11, 12]],
    ]);
  });

  it('respects isExpanded function', () => {
    expect(
      collapseContextBlocks(
        [
          ['!', [0, 1, 0, 2]],
          ['=', [1, 10, 2, 11]],
          ['!', [10, 11, 11, 12]],
        ],
        (aLine, _bLine) => aLine === 4,
      ),
    ).toMatchObject([
      ['!', [0, 1, 0, 2]],
      ['=', [1, 10, 2, 11]],
      ['!', [10, 11, 11, 12]],
    ]);
  });

  it('skips "~" if "=" block is too small', () => {
    expect(
      collapseContextBlocks(
        [
          ['!', [0, 1, 0, 2]],
          ['=', [1, 7, 2, 8]],
          ['!', [7, 8, 8, 9]],
        ],
        () => false,
      ),
    ).toMatchObject([
      ['!', [0, 1, 0, 2]],
      ['=', [1, 7, 2, 8]],
      ['!', [7, 8, 8, 9]],
    ]);
  });

  it('preserves context around empty ! block', () => {
    expect(
      collapseContextBlocks(
        [
          ['=', [0, 5, 0, 5]],
          ['!', [5, 5, 5, 5]],
          ['=', [5, 6, 5, 6]],
        ],
        () => false,
      ),
    ).toEqual([
      ['~', [0, 2, 0, 2]],
      ['=', [2, 5, 2, 5]],
      ['!', [5, 5, 5, 5]],
      ['=', [5, 6, 5, 6]],
    ]);
  });

  it('handles adjacent "=" blocks', () => {
    expect(
      collapseContextBlocks(
        [
          ['=', [0, 2, 0, 2]],
          ['=', [2, 8, 2, 8]],
        ],
        () => false,
      ),
    ).toMatchObject([
      ['~', [0, 2, 0, 2]],
      ['~', [2, 8, 2, 8]],
    ]);
  });
});

describe('mergeBlocks', () => {
  it('should handle empty blocks', () => {
    const result = mergeBlocks([], []);
    expect(result).toEqual([]);
  });

  it('should merge blocks', () => {
    const abBlocks: Array<Block> = [
      ['!', [0, 0, 0, 1]],
      ['!', [0, 0, 1, 4]],
      ['!', [0, 0, 4, 7]],
    ];
    const cbBlocks: Array<Block> = [
      ['!', [0, 0, 0, 2]],
      ['!', [0, 0, 2, 3]],
      ['!', [0, 0, 3, 6]],
      ['!', [0, 0, 6, 7]],
    ];
    const result = mergeBlocks(abBlocks, cbBlocks);
    expect(result).toEqual([['!', [0, 7, 0, 7]]]);
  });

  it('should handle blocks with different signs', () => {
    let abBlocks: Array<Block> = [
      ['!', [0, 1, 0, 1]],
      ['!', [1, 2, 1, 2]],
      ['=', [2, 5, 3, 6]],
    ];
    let cbBlocks: Array<Block> = [
      ['!', [0, 2, 0, 3]],
      ['=', [2, 3, 3, 4]],
      ['=', [3, 5, 4, 6]],
    ];
    let result = mergeBlocks(abBlocks, cbBlocks);
    expect(result).toEqual([
      ['!', [0, 3, 0, 3]],
      ['=', [3, 6, 3, 6]],
    ]);

    abBlocks = [
      ['!', [0, 0, 0, 3]],
      ['=', [0, 4, 3, 7]],
    ];
    cbBlocks = [
      ['=', [0, 1, 0, 1]],
      ['=', [1, 4, 1, 4]],
      ['!', [4, 4, 4, 6]],
      ['=', [4, 5, 6, 7]],
    ];
    result = mergeBlocks(abBlocks, cbBlocks);
    expect(result).toEqual([
      ['!', [0, 3, 0, 3]],
      ['=', [3, 4, 3, 4]],
      ['!', [4, 6, 4, 6]],
      ['=', [6, 7, 6, 7]],
    ]);
  });

  it('should preserve empty ranges', () => {
    const abBlocks: Array<Block> = [
      ['=', [0, 1, 0, 1]],
      ['!', [1, 2, 1, 1]],
      ['=', [2, 6, 1, 5]],
    ];
    const cbBlocks: Array<Block> = [
      ['=', [0, 4, 0, 4]],
      ['!', [4, 5, 4, 4]],
      ['=', [5, 6, 4, 5]],
    ];
    const result = mergeBlocks(abBlocks, cbBlocks);
    expect(result).toEqual([
      ['=', [0, 1, 0, 1]],
      ['!', [1, 1, 1, 1]],
      ['=', [1, 4, 1, 4]],
      ['!', [4, 4, 4, 4]],
      ['=', [4, 5, 4, 5]],
    ]);
  });
});

function renderDiff(
  a: string,
  b: string,
  diffFunc: (aLines: string[], bLines: string[]) => Array<Block>,
): string {
  const aLines = splitLines(a);
  const bLines = splitLines(b);
  const blocks = diffFunc(aLines, bLines);
  return blocks
    .flatMap(([sign, [a1, a2, b1, b2]]) => {
      if (sign === '=') {
        return aLines.slice(a1, a2).map(l => ` ${l}`);
      } else {
        return aLines
          .slice(a1, a2)
          .map(l => `-${l}`)
          .concat(bLines.slice(b1, b2).map(l => `+${l}`));
      }
    })
    .join('');
}
